The present invention relates to image processing, and more particularly to contrast enhancement of images by histogram manipulation.
A digital image is an array, usually a rectangular matrix, of pixels. Each pixel is one picture element and is a digital quantity that is a value that represents some property of the image at the location in the array corresponding to a particular location in the image. Typically, in continuous tone black and white images the pixel values represent a gray scale value.
Pixel values for an image have to conform to a specified range. For example, each array element may be one byte, i.e., eight bits. In that example, the pixel values must range from 0 to 255. In a gray scale image a 255 may represent absolute white and 0 total black.
Color images consist of three color planes, generally corresponding to red, green, and blue (RGB). For a particular pixel, there is one value for each of these color planes, i.e., a value representing the red component, a value representing the green component, and a value representing the blue component. By varying the intensity of these three components, all colors in the color spectrum may be created.
Output devices, such as printers and displays, also have particular ranges for pixel values. A particular device may be configured to accept and output eight-bit image data, i.e., pixel values in the range 0 to 255.
However, many images do not have pixel values that make effective use of the full dynamic range of pixel values available on an output device. For example, in the eight-bit case, a particular image may in its digital form only contain pixel values ranging from 100 to 150, i.e., the pixels fall somewhere in the middle of the gray scale. Similarly, an eight-bit color image may also have RGB values that fall within a range some where in middle of the range available for the output device. The result in either case is that the output is relatively dull in appearance.
The visual appearance of an image can often be improved by remapping the pixel values to take advantage of the full range of possible outputs. That procedure is called contrast enhancement.
There are several prior art contrast enhancement techniques. These techniques are especially common for monochrome (e.g., gray scale) images, such as from medical (e.g., cat-scans, x-rays, and ultrasound) and radar sources. In such applications, contrast enhancement can be used to find image details that would otherwise be difficult to discern.
Contrast enhancement techniques are often based on histogram equalization. In histogram equalization a histogram of gray level distribution of the image is constructed. FIG. 1 is an example of such a histogram. A histogram is a one dimensional array with an array element corresponding to each value in the range of pixel values. Each histogram element contains a count of the number of pixels that has the particular pixel value corresponding to that element. In histogram equalization, the pixel values in the image are altered to make the distribution of gray level values as uniform as possible. Histogram equalization is described in A. K. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, Inc., 1989, pp. 241-243.
A variation of histogram equalization, known as adaptive histogram equalization or local area histogram equalization, uses a sliding window to define an image region for each pixel. The histogram of that region is then equalized to determine the output value for the pixel. Adaptive histogram equalization is described in John B. Zimmerman, et al., An evaluation of the effectiveness of adaptive histogram equalization for contrast enhancement, IEEE Trans. On Medical Imaging, 7 (4):304-312, December 1988. The adaptive histogram equalization procedure is computationally very expensive because a separate histogram is constructed for each image pixel. A number of region-based variants of adaptive histogram equalization have been proposed in Stephen Pizer et al., Adaptive histogram equalization and its variations, Computer Vision, Graphics, and Image Processing, 39 (3):355-368, September 1987; S. S. Y. Lau, Global image enhancement using local information, Electronics Letters, 30 (2):122-123, January 1994; J. A. Stark and W. J. Fitzgerald, Model-based adaptive histogram equalization, Signal Processing, 37:193-200, 1994. These techniques give comparable results to adaptive histogram equalization while reducing computation.
Deficiencies common to adaptive histogram variants are that although some variants reduce computation requirements substantially relative to full-blown adaptive histogram equalization, the required computation is still significant enough to be impractical in many applications.
A further deficiency of adaptive histogram variants is that because these schemes adjust image pixel values locally, the processed image will not retain the relative lightness of pixels from the original image. For example, some details in a shadow region may be lightened to the point where these details are lighter than sunlit parts of the same image. The uneven lightening/darkening of an image leads to unacceptable visual appearance in photographic images.
A generalization of histogram equalization, known as histogram specification, adjusts the data so the output histogram has a distribution close to some desired distribution. Histogram specification is described in Jain, supra, page 243.
Color image enhancement is considerably more complicated. Color images consist of three color planes, generally corresponding to red, green, and blue (RGB). One simple color image enhancement technique (described in P. E. Trahanias and A. N. Venetsanopoulos, Color image enhancement through 3-d histogram equalization, 11th IAPR Conference on Pattern Recognition, Conference C: Image, Speech, and Signal Analysis, pp. 545-548, September 1992) is to perform histogram equalization on each color independently. However, that technique can cause large color shifts and other undesirable artifacts in the image.
One histogram-based contrast enhancement technique that attempts to avoid such artifacts is to construct a three dimensional histogram and perform modifications in all three dimensions jointly. That technique is described in Trahanias and Venetsanopoulos, above, and in Phillip A. Mlsna and Jeffrey J. Rodriguez, Explosion of multidimensional image histograms. IEEE International Conference on Image Processing, Vol III, pp. 958-962, Austin, Tx., November 1994. Unfortunately, the required computation for the technique of joint modification of a three-dimensional histogram is at least on the order of the number of occupied histogram bins, which can number in excess of a hundred thousand for a moderately large image. This approach is therefore computationally intensive and hence not very practical.
Other approaches, including the preferred embodiment of the present invention, transform the image data into some luminance-chrominance color space and perform the enhancement in this domain. Some techniques adjust only the luminance histogram, while others adjust both luminance and chrominance histograms. Straightforward histogram equalization on the luminance component can cause undesirable artifacts in the output image. Specifically, large areas of approximately equal luminance can suffer from contouring artifacts, while an especially dark (light) background can cause the foreground objects to become too light (dark). Some of the more complicated enhancement procedures require that the image data undergo a nonlinear transformation before processing, which increases the computational complexity. Histogram equalization of luminance or chrominance histograms is described in Robin N. Strickland, et al., Digital color image enhancement based on the saturation component, Optical Engineering, 26 (7):609-616, July 1987, and in Ilia M. Bockstein, Color equalization method and its application to color image processing, Journal of the Optical Society of America A, 3 (5):735-737, May 1986.
Histogram manipulation has also been used for purposes other than contrast enhancement. For example, for monochrome images, multi-thresholding techniques have been developed for dividing a histogram into clusters. The resulting clusters are then used to segment the image into regions corresponding to various objects and backgrounds. Such clustering techniques are described in P. K. Sahoo, et al., A survey of thresholding techniques, Computer Vision, Graphics, and Image Processing, 41 (2):233-260, February 1988. If the histogram contains flat regions of low amplitude between higher peaks, for example, a threshold value anywhere in the flat region would give nearly the same segmentation of the image. For the purpose of contrast enhancement, it is desirable to differentiate between regions of high activity and regions with little activity. Consequently, it is desirable to divide the histogram such that flat regions of low amplitude form separate clusters. Therefore, the multi-thresholding clustering techniques are not suited to color contrast enhancement.
Accordingly, it is desirable to have a contrast enhancement technique that is not computationally intensive and does not introduce undesirable artifacts in the output image.
A first embodiment of the invention is a method of operating a computer to produce contrast enhanced digital images. The method commences with the step of producing a histogram having a first axis corresponding to a measurable property (e.g., luminance) and a second axis corresponding to a count of pixels having a particular value for the measurable property. This histogram is divided into clusters and histogram equalization or stretching is performed on each cluster thereby producing a modified histogram. The modified histogram is used to adjust the value of said first measurable property in said digital form, thereby producing a contrast enhanced image.
In one embodiment of the invention the histogram is divided into clusters using a pattern matching technique. For example, patterns in the histogram that resemble gaussian distributions and patterns that resemble uniform distributions are separated into individual clusters.
In another embodiment of the invention, the histogram is partitioned into clusters of equal size.
In a further embodiment of the invention, subsequent to dividing the histogram into clusters, the cluster boundaries are remapped proportionally to the cluster""s range, the number of pixels in the range, the total number of pixels in the image, and the histogram extent.
In another embodiment of the invention, some other property (e.g., chrominance) of the image is used to limit the values of the modified histogram.
In a further embodiment, the invention is practiced on a computer system for image processing having a histogram producing unit operable to produce a histogram data structure in a memory on the computer system. The computer system further contains a clusterizer connected to the histogram data structure and is operable to partition the histogram data structure into clusters. A histogram cluster boundary adjuster is connected to the histogram data structure and is operable to adjust boundaries of each cluster in said data structure such that said boundaries conform to a function having the parameters cluster width (Ro), a count of pixels in the cluster (Ni), a count of pixels in the image (Nt), the original histogram extent (Eo), and a desired histogram extent (Ed). A histogram adjuster is also connected to said histogram data structure and is operable to modify the histogram for each such cluster according to a desired characteristic.
In another embodiment of the invention, the clusterizer partitions the histogram data structure into equal size clusters.